编译原理 复习

前言

  这篇文章是《编译原理》课程的复习笔记，可以作为期末考试的复习资料。

编译原理 大纲

graph TD
    SC(Source Code 源代码)-->LA
    subgraph Front End 前端
        LA[Lexical Analysis 词法分析]--Token Stream-->SA
        SA[Syntax Analysis 语法分析]--Syntax Tree-->SA'
    end
    subgraph Back End 后端
        SA'[Semantic Analysis 语义分析]--Syntax Tree-->ICG
        ICG[Intermediate Code Generation 中间代码生成]--IR-->CO
        CO[Code Optimization 代码优化]--IR-->CG
    end
        CG[Code Generation 目标代码生成]-->TC(Target Code 目标代码)

绪论

编译 定义

将高级语言（源语言）翻译成汇编语言或机器语言（目标语言）的过程。

词法分析（Lexical Analysis）

定义

扫描源程序的字符流，识别并分解出有词法意义的单词或符号（称为 token）

• 输入：源程序
• 输出：token 序列（词法单元）
• token 表示：<类别, 属性值>
  • 保留字、标识符、常量、运算符等
  • 将各成分按其在语言中的作用分类

例如 z=1 进行词法分析之后得到

1
2
3

<Id, 'z'>
<Op, '='>
<Num, '1'>

执行

  词法分析如何执行？

• 识别子串所属的 token 类别
• 返回 token 单元

问题：输入串具有二义性，如何进行识别？

正则表达式（RE）

• Alphabet 字母表：一个有限的符号集
• String 串：一个由字母表中符号组成的有限句子
• Language 语言：字母表中符号组成的串的集合

  我们需要一种规范化的语言来对 token 进行识别 —— 正则表达式

• 原子（atomic）
  • $\epsilon$（空串）
  • 单个字符
• 组合形式（compound）
  • Union（并）：$A|B=\{s|s\in A or s\in B\}$
  • Concatenation（连接）：$AB=\{ab|a\in A\; and\; b\in B\}$
  • Iteration（迭代）：$A^*=\cup_{i\geq0}A^i\;where\;A^i=A…A(i\;times)$
    • $A^*=\{\epsilon\}+A+AA+AAA+…$
    • $A+=A+AA+AAA+…=AA^*$
  • $(A)\equiv A$：$A$ 是一个正则表达式
  • 优先级从低到高
• 一些其他的表示形式
  • Union（并）：$A|B\equiv A+B$
  • Option（选择）：$A?\equiv A+\epsilon$
  • Range（区间）：$’a’+’b’+’c’+…+’z’\equiv[a-z]$
  • Excluded range（排除区间）：$[a-z]$ 的补集 $[\hat{\;}a-z]$

字母表运算

• Product（乘积）：$\sum_1\sum_2=\{ab|a\in\sum_1,b\in\sum_2\}$
• Power（幂）：$\sum^n=\sum^{n-1}\sum,n\geq1;\sum^0=\{\epsilon\}$
• Positive Closure（正闭包）：$\sum^+=\sum\cup\sum^2\cup\sum^3\cup…$
• Kleene Closure（闭包）：$\sum=\sum^0\cup\sum^+$

有穷自动机（Finite Automata）

定义

  自动机指一个机器或者一个程序，有穷自动机指一个状态有限的自动机。

状态转移

• 拥有状态结点和带标签的边
• 有且只有一个起点状态，有一个或多个终点状态

NFA（不确定有穷自动机）

• 对于给定的一个状态和一个输入可以有多个转移方向
• 可以空边的状态转移
• 可以选择转态转移的方向

DFA（确定有穷自动机）

• 一个状态一个输入对应一个转移方向
• 没有空边的状态转移
• 对于一个串只有唯一的状态转移路径

词法分析过程

graph LR
    LS(词法分析)-->RE
    RE-.转换.->NFA
    NFA-.转换.->DFA
    RE--转换-->DFA
    DFA--最小化-->MDFA[Minimized DFA]
    MDFA-->LA(词法分析器)

RE 转换为 NFA

• 自顶向下逐步分解 Top-Down
• 自下而上组合法 Bottom-Up

NFA 转换为 DFA

• 找出 $\epsilon$ 闭包以消除 $\epsilon$ 边
• 对于不确定的状态转移构造子集
• 使用表驱动法

DFA 的最小化

• 找出 DFA 中的等价类
• 将所有的等价类进行合并
• 状态数最少的 DFA 就是最小 DFA

语法分析（Syntax Analysis）

定义

从词法分析器输出的 token 序列中识别出各类短语，并构造语法分析树（paser tree）

• 输入是来自词法分析的 token 序列
• 输出是一棵语法分析树
• 不是所有输入的 token 序列都是合法的（需要进行判别）
• 如何表明语法？（RE/FA？它们无法表示嵌套结构）

文法（Grammar）

定义

系统地描述程序语言结构的语法，例如表达式和声明语句。
形式化定义：由4个部分组成 $\{T, N, s, \sigma\}$

• $T$：终结符
  • 构成串的基本符号
  • 不能单独出现在推导式左边（不能再进行推导）
  • 语法分析树中的叶子结点
• $N$：非终结符
  • 不是终结符的其他符号
• $s$：开始符号
  • 一种非终结符
• $\sigma$：产生式
  • 指定终结符和非终结符组成串的形式

文法推导

• 产生式规则：LHS $\rightarrow$ RHS，表示 LHS 可以由 RHS 构建（代替）
• 推导（Derivation）：一系列对于产生式规则的应用
  • 最左推导：每次推导代替最左的非终结符
  • 最右推导：每次推导代替最右的非终结符
• 句型（Sentential form）：句型可以包含终结符和非终结符（也可以为空）
• 句子（Sentence）：句子只包含终结符
• 语言（Language）：由文法产生

文法归约

• 文法推导的逆过程
• 从 RHS 归约到 LHS

分析树

分析树即是使用图表示的推导过程

• 最左推导：从左到右建树
• 最右推导：从右到左建树

如果一个文法是二义性的（Ambiguity），则它可能对同一个句子产生多棵分析树。
对于大多数语法分析器来说，非二义性文法是更好的。

文法类型

• 0 型文法：无限制文法
  • LHS 不能为 $\epsilon$
• 1 型文法：上下文有关文法（CSG）
  • LHS 的长度与 RHS 相等或更短
  • RHS 不能为 $\epsilon$
• 2 型文法：上下文无关文法（CFG）
  • LHS 是单独的非终结符
  • RHS 不能为 $\epsilon$
• 3 型文法：正则文法
  • LHS 是单独的非终结符
  • RHS 是一个终结符或者一个终结符跟着一个非终结符
• 由上到下具有包含关系

消除二义性

• 重写文法，消除二义性
• 使用二义性文法，但是同时需要制定非二义性的规则

如何消除二义性？

• 指定优先级（Precedence）
• 指定结合性（Associativity）
  • 左结合
  • 右结合

自顶向下分析（Top-Down）

特点

• 从根结点开始
• 试图将开始符号展开成为输入串
• 使用最左推导
• 递归下降分析（RDP）
  • 带有回溯（Backtracking）
  • 带有预测分析（Predictive parser）（向前看）【常用】
  • 无法解决左递归问题（需要进行消除左递归）

预测分析

• 左递归
  • 消除左递归
• 共同前缀
  • 提取左公因子
  • 使用 First 集
    • 解决回溯问题
    • 新的问题：引入了大量的新非终结符和 $\epsilon$ 产生式
  • 使用 Follow 集
    • 解决空字问题

LL(k) 含义

• L：从左到右扫描
• L：最左推导
• k：向前看 k 个符号

LL(1) 文法

上面提到的构造不带回溯的自上而下的语法分析，就是 LL(1) 文法的条件。

• 文法不含左递归
• 文法中每一个非终结符的各个产生式的 First 集两两不相交
• 文法中每一个非终结符 A，若 $\epsilon\in$ First(A)，则 First(A) $\cap$ Follow(A) 为空

表驱动分析

• 输入缓冲区：包含待分析的串，由 \$ 开始
• 栈：保存未匹配的推导串
• 分析表：记录推导过程的表
• 分析驱动：下一步动作基于栈顶或者当前 token

其他 LL 文法

• LL(0)：没有预测分析，一个非终结符只能生成一个规则，一个语言只能生成一个串
• LL(2) 乃至 LL(k)：分析表的大小 $O(|N|*|T|^k)$，其中 $N、T$ 分别是非终结符和终结符的数量。

自底向上分析（Bottom-Up）

特点

• 从叶子结点开始
• 试图将输入串归约到开始符号
• 使用最右推导的逆（也称为最左归约、规范归约）
• 比 Top-Down 更强大
  • 不需要提取左因子
  • 可以解决左递归问题
  • 可以表达多个语言
  • 效率更高
• 使用移入-归约（Shift-Reduce）

移入-归约（Shift-Reduce）

• 移入：将 # 右移，移入一个新符号
• 归约：反向应用生成式，将生成式右边归约为左边的状态
  • 将 0 或多个符号从栈中弹出
  • 将相应的非终结符压到栈中
• 接收：栈中只包含开始符号、输入缓冲区为空，完成语法分析
• 报错：发现语法错误，无法继续进行语法分析，调用一个错误恢复子例程

句柄（Handle）

• 句型的最左直接短语
• 每次对句柄进行归约

LR(k) 含义

• L：从左到右扫描
• R：最右推导的逆
• k：向前看 k 个符号

LR 自动机

• 句柄总是在栈顶
• 移入-归约策略
  • 栈顶没有句柄，进行移入
  • 栈顶含有句柄，进行归约，变成一个非终结符
  • 可以使用一个移入-归约分析表进行记录
• 可能产生冲突
  • 如果移入和归约都合法，则产生移入-归约冲突
  • 如果同时存在两种或以上合法的归约，则产生归约-归约冲突
• LR 语法分析器使用两张表
  • 动作表 Action[s, a]，栈顶状态是 s 而下个输入的 token 是 a
    • 接受终结符
    • 移入、归约、接收、报错
  • 跳转表 Goto[s, X]，非终结符 X，栈顶状态 s
    • 接受非终结符
• 增广文法（Augmented Grammar）
  • 在开始符号 S 前面加入一个 S’
  • S’ $\rightarrow$ .S 作为初始状态
  • S’ $\rightarrow$ S. 作为接受状态
  • 保证表中只有一个 acc（接受）状态

几种 LR 文法

• LR(0)
  • 只对栈顶考虑移入/归约
  • 最弱，由于其局限性使用不多，非常容易发生冲突
• SLR(1)
  • 简单的 LR，基于 LR(0)，归约时使用 Follow 集
  • 动作表和跳转表保持和 LR(0) 一样小
  • 只是简单的考察下一个输入符号是否属于归约项目相关的 Follow 集
  • 依然容易产生冲突
• LR(1)
  • 向前看一个 token
  • 对比 LR(0) 更复杂，有更大的表
• LALR(1)
  • 向前看的 LR(1)，寻找具有相同核心的 LR(1) 项集并进行合并
  • 根据合并后得到的项集族构造语法分析表
  • 分析表比 LR(1) 更小
  • 不会引入移入-归约冲突
  • 会引入归约-归约冲突
  • 延迟错误识别

语义分析（Semantic Analysis）

定义

收集标识符的属性信息，并进行语义检查，上下文相关分析。

• CFG 是上下文无关的，不能分析上下文信息
• 语义检查包括变量需要先声明后使用、变量类型一致、表达式类型一致等等

符号表（Symbol Table）

定义

跟踪程序的所有符号信息的一种编译器的数据结构

• 记录每个符号的信息
• 在语义分析阶段创建
• 在词法分析阶段准备
• 在代码生成阶段使用
• 在生成二进制流后丢弃

程序变量（Variable）

• 声明（declaration）：类型和名字
• 定义（definition）：内存空间分配
• 绑定（binding）：使用定义匹配标识符
• 作用域（Scope）：可以绑定定义的程序区域
  • 静态作用域：一个声明起作用的那段区域
    • 绑定最近封闭区域的定义
    • 拥有更少的程序错误
    • 拥有更高效的代码
  • 动态作用域：运行时决定
    • 绑定当前执行中的最新定义
    • 在运行时才进行绑定
    • 难以直接通过观察判断

符号表信息

• 串：标识符名称
• 类型：变量、函数、结构体、类
• 信息
  • 变量：类型、地址
  • 函数：返回类型、进入地址
  • 结构体：域内变量名、域内变量类型
  • 类：类的符号表

维护

• 进入作用域
• 退出作用域
• 发现符号
• 添加符号
• 检查符号

结构

符号表访问的时间影响编译前端的性能

• 线性表
  • 数组：插入删除 $O(n)$，搜索 $O(n)$，没有空间浪费
  • 链表：插入删除 $O(1)$，搜索 $O(n)$，需要额外的指针空间
• 二叉树
  • 插入删除搜索均是 $O(\log n)$，最坏情况下会退化成链表
  • 比线性表需要更多的空间
• 哈希表
  • 插入删除搜索均是 $O(1)$，当哈希冲突过多链过长时退化成 $O(n)$

处理多个作用域

栈方法

• 每个作用域维护一个单独的符号表
• 对于每个开放的作用域维护一个入口
• 进入一个作用域时符号表指针入栈
• 退出一个作用域时符号表指针出栈
• 缺点
  • 因为需要查找多个哈希表，查找比较低效（所有的全局变量都在栈底）
  • 因为需要维护多个哈希表，对内存的使用比较低效

链方法

• 对所有的作用域只维护一个符号表
• 进入一个作用域时标记一个新的嵌套层次
• 退出一个作用域时将该嵌套层次的所有符号删除
• 符号表只维护当前活跃的作用域
• 作用
  • 只适用于块作用域，不适用于类作用域
  • 退出作用域时开销较大（需要进行删除）
  • 查找时只需要一个哈希表
  • 存储在内存里的只是一个大的哈希表

类型检查

• 静态类型检查：编译时（C/C++，Java）
  • 有一些类型错误是无法在编译时就发现的
  • 程序需要更严格的编写规范
  • 通常程序 bug 更少，运行时间更快
• 动态类型检查：执行时（Python，JavaScript，PHP）
  • 在执行时再检查可以发现更多错误，更可取
  • 程序无需那么严格的规范
  • 更多的程序 bug 和更长的运行时间

语法制导翻译（Syntax Directed Translation，SDT）

定义

使用 CFG 来引导对语言的翻译，是一种面向文法的翻译技术

语法制导定义（Syntax Directed Definitions，SDD）

定义

SDD 是对 CFG 的推广，翻译的高层次规则说明

• 将每个文法符号和一个语义属性集合相关联
• 将每个产生式和一组语义规则相关联

副作用（Side effect）

• 一般属性值计算之外的功能
• 例如：代码生成、打印结果、修改符号表

属性文法（Attribute grammar）

• 一个没有副作用的 SDD
• 属性文法的规则仅仅通过其他属性值和常量来定义一个属性值

标注分析树（Annotated parse-tree）

• 每个结点都带有属性值的分析树

文法符号的属性

• 综合属性
  • 分析树结点 N 上的非终结符 A 的综合属性只能通过 N 的子结点或 N 本身的属性值来定义
  • 终结符可以具有综合属性
• 继承属性
  • 分析树结点 N 上的非终结符 A 的继承属性只能通过 N 的父结点、N 的兄弟结点或 N 本身的属性值来定义
  • 终结符没有继承属性

产生式中的属性依赖

依赖图

• 依赖图决定属性值的计算
• 依赖图描绘了分析树的属性信息流

SDD 的求值顺序

• 按照属性之间的依赖关系
• 在对一个结点属性求值之前，必须首先求出这个属性值所依赖的所有属性值
• 通过依赖图的边确定计算顺序
• 使用依赖图的拓扑排序
• 非常难确定是否有循环依赖

S-属性定义

• 只具有综合属性
• 可以使用任何自底向上的顺序计算属性值
• 可以在 LR 分析中实现

L-属性定义

• 依赖图的边只能从左到右
• 每个属性要么是一个综合属性，要么是满足以下条件的继承属性
  • 对于产生式 $A\rightarrow X_1X_2…X_n$，$X_i$ 的继承属性仅依赖下列属性
    • $A$ 的基础属性
    • 产生式中 $X_i$ 左边的符号 $X_1,X_2,…,X_i$ 的属性
    • $X_i$ 本身的属性，但不能在依赖图中形成环路
• 可以在 LL 分析中实现

语法制导翻译方案（Syntax Directed Translation Scheme，SDT）

定义

• SDT 是在产生式右部嵌入了程序片段的 CFG，这些程序片段称为语义动作
• SDT 是 SDD 的补充，是具体翻译的实施方案
• SDT 显式地指明了语义规则的计算顺序，以便说明某些细节

具体实现

• 基于预先构建的分析树
• 在语法分析过程中实现

S-SDD 到 SDT 的转换

• 将每个语义动作都放在产生式的最后
• 使用 LR 语法分析实现，当归约发生时执行相应的语义动作

L-SDD 到 SDT 的转换

• 将计算某个非终结符 A 的继承属性的动作插入到产生式右部中紧靠在 A 的本次出现之前的位置上
• 将计算一个产生式左部符号的综合属性的动作放置在这个产生式右部的最右端
• 可以在 LL 或 LR 语法分析过程中实现
  • 递归预测分析
    • 综合属性：最后计算
    • 继承属性：参数传递
  • 非递归预测分析
    • 扩展语法分析栈
    • 管理属性信息
  • LR 分析

中间代码生成（Intermediate Code Generation）

定义

编译器翻译源程序并生成一些中间表示形式（Intermediate Representation，IR），再将其转化为机器代码

IR 的好处

• 增加程序的抽象性（比起机器代码）
• 前后端分离（与不同高级程序语言、不同处理器架构无关）
• 目标重定向
• 易于优化和扩展

高层 IR：更趋向高级程序语言

• 抽象语法树（AST）
• 分析树

低层 IR：更趋向集成

• 三地址码
• 静态单赋值

机器层 IR：趋向机器

• x86 IR
• ARM IR
• MIPS IR

三地址码（Three-Address Code，TAC）

• 每个操作最多具有三个操作数
• 可以是变量、常量、临时变量
• 长表达式可以转换成多条指令
• 控制流，跳转
• 与机器无关
• 目标：做出更简单的与机器无关的优化

操作

• 二元赋值
• 一元赋值
• 拷贝
• 无条件跳转
• 条件跳转
• 过程调用
• 过程调用返回
• 索引
• 地址和指针

执行

• 四元式（quadruples） op arg1, arg2, result
• 三元式（triples） op arg1 arg2
• 间接三元式（indirect triples） op arg1 arg2

静态单赋值（Single Static Assignment，SSA）